package com.leetcode.p0;

import java.util.HashMap;

public class Test70_2 {

    private HashMap<Integer, Integer> hashMap = new HashMap<>();

    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }

        int a = 0;
        int b = 0;
        if (hashMap.containsKey(n - 1)) {
            a = hashMap.get(n - 1);
        } else {
            a = climbStairs(n - 1);
            hashMap.put(n - 1, a);
        }

        if (hashMap.containsKey(n - 2)) {
            b = hashMap.get(n - 2);
        } else {
            b = climbStairs(n - 2);
            hashMap.put(n - 2, b);
        }
        return a + b;
    }

    public static void main(String[] args) {
        Test70_2 test = new Test70_2();
        int result = test.climbStairs(45);
        System.out.println(result);
    }

}
